package 链表;

public class No19删除链表的倒数第N个节点 {

    /**
     * 给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
     *
     * 示例：
     * 给定一个链表: 1->2->3->4->5, 和 n = 2.
     * 当删除了倒数第二个节点后，链表变为 1->2->3->5.
     * 说明：
     * 给定的 n 保证是有效的。
     * 进阶：
     * 你能尝试使用一趟扫描实现吗？
     */

    /**
     * 1.easy的解法,遍历两次,第一次记录链表的长度,第二次根据长度算出n对应的正序,再遍历着去删除一次
     * 2.不算空间复杂度的话,可以用Map以k为index,value为node来达到一趟扫描实现;
     * 3.用两个指针,先让fast走n步,然后再让slow开始一起和fast走,当fast达到null时,
     *   那么fast.index-slow.index=n,就找到了目标节点。
     */

    public static ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode listNode=new ListNode();
        listNode.next=head;

        ListNode slow=listNode;
        ListNode fast=listNode.next;

        int index=0;

        while (index<n){
            fast=fast.next;
            index++;
        }

        while (fast!=null){

            fast=fast.next;
            slow=slow.next;

        }

        ListNode next=slow.next;
        slow.next=next.next;
        next.next=null;//脱离链表

        return listNode.next;
    }

    public static void main(String[] args) {
        int[] arr=new int[]{1,2,3,4,5,6,7};
        ListNode listNode = ListNode.createListNode(arr);
        ListNode result = removeNthFromEnd(listNode, 2);
        ListNode.printListNode(result);
    }

}
